The present invention relates in general to computer network devices which selectively direct packets among a plurality of ports, and in particular to such a device where packets are queued using two different types of memory.
In network switch devices, incoming packets must be sent out on different ports. The speed or rate at which packets arrive is not always equal to the speed or rate at which packets can be sent out. This occurs for various reasons such as different types of links delivering and removing the packets from the network switch at different rates, and different speeds of operation of the devices at the other end of the link. The rate of packet flow also various widely because of such factors as how busy the devices on the other end of the link are, and the operations being performed by these devices. When the incoming rate of packets is larger than the outgoing packet rate, packets can be lost. The end devices must then re-request these packets. This increases the overall communication time for a message across the network, and increases the traffic across the network. An increase in traffic increases the likelihood of incoming rates being higher than outgoing rates, which then increases the likelihood of more dropped packets.
In order to reduce the likelihood of dropped packets, and to take advantage of the widely varying packet transfer rates, buffers are used to temporarily store or cache the packets. When the incoming rate is larger than the outgoing rate, the extra packets are stored in a buffer. Subsequently, when the outgoing rate is higher than the incoming rate, the excess packets are removed from the buffer. The larger the buffer, the larger the incoming rate can be than the outgoing rate, and the longer this inequality can exist without losing packets. The larger the packets, the larger is the expense, and the larger is the size of the memory.
In network switch products today there is a new emphasis on providing quality/class of service. Network devices will need to classify and mark packet streams with the required quality/class of service. Therefore computer network switches will be required to have more buffers per port. This increases the amount of memory needed for buffering the input and output rates to avoid lost packets. This increase in the amount of memory also increases the cost and space required for network switches. The nature of computer network communication, and packet transfer, makes it desirable to provide the buffers in memory devices having fast access times.
It is a primary object of the present invention to provide a buffer for packets which has a fast access time, and uses two different types of memory devices in order to reduce the size and cost of computer network switches and/or increase buffer size and efficiency.
The computer network switch includes a receiving module for receiving a plurality of packets, and determining a type (port and/or class) of each of the packets. A packet memory includes a plurality of buffer cells receiving the plurality of packets from the receiving module. Each of the buffer cells has a buffer descriptor identifying a respective buffer cell. A descriptor free pool lists available buffer descriptors that can be used for new incoming packets. A plurality of transmit queues hold the buffer descriptors in a first in first out order for the transmission queuing of their respective buffer cells and respective packets. Each of the transmit queues corresponding to one of the types of packets, and each transmit queue includes an input queue, an expansion queue and an output queue.
The switch also includes control logic for directing the removing of one of the available buffer descriptors from the free pool and directing one of the packets from the receiving module into one of the buffer cells corresponding to the one available buffer descriptor. The control logic places the one buffer descriptor in the input queue of one of the transmit queues corresponding to the type of the one packet.
The control logic also monitors a load status of the input and output queues for each of the transmit queues and selectively directs a flow of the buffer descriptors from the input queue to either the expansion queue or the output queue. In particular, the control logic directs the flow of buffer descriptors to the expansion queue when a load status of the input and output queues are above a predetermined load or threshold.
When the load is below the determined load, usually a lower packet rate than the combined capacity of the input and output queues, the control logic directs the packets directly from the input queue to the output queue. When the load is above the predetermined load level, the control logic directs the buffer descriptors from the input queue to the expansion queue, and then to the output queue.
The input and output queues are preferably formed using SRAM type memory devices because of their fast access time. The expansion memory is preferably formed from DRAM type memory devices because of their respective higher memory density. The control logic also preferably sets the predetermined load level, and controls the packet transfer, so that packets can be delivered to the expansion queue in a burst write, and packets can be removed from the expansion queue in a burst read. This averages out the read and write time to prevent significant slowing of the buffer descriptors though the transmit queue.
A transmit module controls the plurality of ports for transmitting the packets onto the computer network. Each of the transmit queues for each port corresponds to at least one of the types of packets. The transmit module removes a first out buffer descriptor from the output queue of one transmit queue and removes the packet from the buffer cell corresponding to the first out buffer descriptor.
The descriptor free pool can also include an input queue, and expansion queue and an output queue. When a buffer descriptor is needed, the control logic removes a buffer descriptor from the output queue of the free pool. When the transmit queue is finished with a buffer descriptor, the control logic directs the buffer descriptor to the input queue of the descriptor free pool. The control logic monitors the load level of the queues in the descriptor free pool. When the load level is above a predetermined level, the control logic directs buffer descriptors from the input queue to the expansion queue, and then to the output queue. When the load level is below a predetermined level, the control logic directs buffer descriptors directly from the input queue to the output queue.
The control logic is also able to adjust the size of the expansion queue. This is very helpful in customizing a network switch. Different users may have different needs and therefore a particular destination may receive more packets of a particular class than other classes, or other users. As an example, one destination may be receiving predominantly time sensitive packets such as streaming audio or video, while another destination may be receiving predominantly time insensitive packets, such as file transfers and email. The present invention allows the input and output queues to be of a minimum size to maintain the fast access times with the size of the expansion queues to be variable to adjust for the needs of the user. This allows for efficient allocation of memory in response to varying needs of the users, and an economical computer network switch in terms of cost and size.
Most next generation network switches will be designed to support quality of service (differentiated services). Quality of service is required to support applications such as voice over IP and video streaming. The support of differentiated services requires many more queues per port. This invention provides a low cost, flexible implementations of a large quantity of queues.
The various features of novelty which characterize the invention are pointed out with particularity in the claims annexed to and forming a part of this disclosure. For a better understanding of the invention, its operating advantages and specific objects attained by its uses, reference is made to the accompanying drawings and descriptive matter in which preferred embodiments of the invention are illustrated.